768E - Game of Stones - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long int LL;
typedef long double LD;
#define nl '\n'
#define ff first
#define ss second
#define inf INT_MAX
#define pb push_back
#define GCD(a, b) __gcd(a, b)
#define PI 2.0 * acos(0.0)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define mem(a, b) memset(a, b, sizeof(a))
#define srtv(v) sort(v.begin(), v.end())
#define unq(v) v.erase(unique(v.begin(),v.end()),v.end());
#define Rep(i, a, b) for (int i = a; i <= b; i++)
#define rep(i, a, b) for (int i = a; i >= b; i--)
#define FOR(i, a) for (int i = 0; i < a; i++)
// #pragma                 GCC optimize("Ofast,no-stack-protector")
// #pragma                 GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma                 GCC optimize("unroll-loops")
#define boost                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define file_inout                         \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout)
#define si(x) scanf("%d", &x)
#define pi(x) printf("%d", x)
#define sss(str) scanf("%s", str)
#define pl(x) printf("%lld", x)
#define sl(x) scanf("%lld", &x)
#define sii(x, y) scanf("%d %d", &x, &y)
#define sll(x, y) scanf("%lld %lld", &x, &y)
#define siii(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define slll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
using    namespace __gnu_pbds;
using namespace std;
//Graph direction array[4]
//int dx[]={0,0,-1,1};
//int dy[]={1,-1,0,0};
//Graph direction array[8]
//dx[]={0,0,1,-1,-1,1,1,-1};
//dy[]={1,-1,0,0,-1,-1,1,1};
//Bishop direction array[8]
//dx[]={0,0,1,-1,-1,1,1,-1};
//dy[]={1,-1,0,0,-1,-1,1,1};
//Knight Direction array[8]
//dx[]={1,1,2,2,-1,-1,-2,-2};
//dy[]={2,-2,1,-1,2,-2,1,-1};
inline long long int MOD(long long int a, long long int m){a=a%m;if(a<0)a+=m; return a;}
#define popcountL __builtin_popcountll
#define popcount __builtin_popcount
inline bool checkBit(int N, int pos){return (bool)(N & (1 << pos));}
inline int setBit(int N, int pos) { return N = N | (1 << pos); }
inline int unsetBit(int N, int pos) { return N = (N & (~(1 << pos))); }
inline int toggleBit(int N, int pos) { return N = (N ^ (1 << pos)); }
// mt19937 rng((uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
// inline int rand(int l, int r){uniform_int_distribution<int> RNG(l,r);return RNG(rng);}
// random() will generate a random value
// random_device rd;
// mt19937 random(rd());
/** Debugging**/
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
    #define debug(x)
#endif

void _print(long long t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(float t) {cerr << t;}
void _print(bool t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------code starts here---------------------------------------
const int maxn = 1e6 + 5;
struct chash {
   static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
   }
 
   size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
   }
};
map<LL,int>dp[61];
int fun(int n,LL mask)
{
    if(n==0)
        return 0;
    if(dp[n].find(mask)!=dp[n].end())
        return dp[n][mask];
    unordered_set<int>st;
    for(LL i=0;i<n;i++)
    {
        if(mask&(1LL<<i))
        {
            st.insert(fun(n-i-1,mask^(1LL<<i)));
        }
    }
    int mex=0;
    while (st.find(mex)!=st.end())
    {
        mex++;
    }
    return dp[n][mask]=mex;
}
void solve(int test)
{
    int n,x,xr=0;
    si(n);
    Rep(i,1,n)
    {
        si(x);
        xr^=fun(x,(1LL<<x)-1);
    }
    if(xr==0)printf("YES\n");
    else printf("NO\n");
}
int main()
{
    int t = 1;
    //si(t);
    Rep(test, 1, t)
    {
        solve(test);
    }
    return 0;
}